package leetcode_1001_1100;

import java.util.HashMap;
import java.util.Map;

public class LeeCode_1092_2_failed {
    public static void main(String[] args) {
        System.out.println(shortestCommonSupersequence("abac", "cab"));
//        System.out.println(shortestCommonSupersequence("abc", "aaabcaa"));
//        System.out.println(shortestCommonSupersequence("bcacaaab", "bbabaccc"));
//        System.out.println(shortestCommonSupersequence("abababab", "aaaaaa"));
//        System.out.println(shortestCommonSupersequence("bcaaacbbbcbdcaddadcacbdddcdcccdadadcbabaccbccdcdcbcaccacbbdcbabb",
//                "dddbbdcbccaccbababaacbcbacdddcdabadcacddbacadabdabcdbaaabaccbdaa").length());
    }

    private static String shortestCommonSupersequence(String str1, String str2) {
        int m = str2.length();
        int n = str1.length();
        boolean[][] dp = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = str1.charAt(j) == str2.charAt(i);
            }
        }
        int[][] oj = new int[m][n];
        oj[m - 1][n - 1] = dp[m - 1][n - 1] ? 1 : 0;
        for (int i = m - 2; i >= 0; i--) {
            oj[i][n - 1] = (dp[i][n - 1] ? 1 : 0) + oj[i + 1][n - 1];
        }
        for (int j = n - 2; j >= 0; j--) {
            oj[m - 1][j] = (dp[m - 1][j] ? 1 : 0) + oj[m - 1][j + 1];
        }
        for (int j = n - 2; j >= 0; j--) {
            for (int i = m - 2; i >= 0; i--) {
                int self = dp[i][j] ? 1 + oj[i + 1][j + 1] : -1;
                int r = oj[i][j + 1];
                int d = oj[i + 1][j];
                if (self >= r && self >= d) {
                    oj[i][j] = self;
                } else if (r >= self && r >= d) {
                    oj[i][j] = r;
                } else {
                    oj[i][j] = d;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                oj[i][j] = (m - i) + (n - j) - oj[i][j];
            }
        }
        return null;
    }
}
